package sudoku;

import java.util.Collections;
import java.util.LinkedList;
import java.util.Map;
import java.util.TreeMap;

/** Class represents Sudoku game board which holds all cell objects.
 *
 * @author Taras Basiuk
 * @version 0.1
 * 
 * @todo sudoku.Cell.addToPossibleValues now returns boolean. 
 * Need to check returns when calling to it.
 */
public class DataGrid implements Cloneable{


    /** This map contains references to cell objects with key values
     * corresponding to 'rowPosition' value of cell. */
    private Map<Integer, Cell> rows;

    /** This map contains references to cell objects with key values
     * corresponding to 'columnPosition' value of cell. */
    private Map<Integer, Cell> columns;

    /** This map contains references to cell object with key values
     * corresponding to 'squarePosition' value of cell. */
    private Map<Integer, Cell> squares;

    /** @todo Change to ArrayList !!!!!!!
     *  Linked list contains references to cell objects, usually sorted.
     *  Used to pick cell with least available possible values. */
    private LinkedList<Cell> possibleValues;

    /** Value which stores number of unsolved cell on the board. */
    private int unsolvedCells;

    /** Default constructor. Creates 81 cell and fills corresponding maps and
     list with references to these cells. Sets number of unsolved cells to 81.*/
    public DataGrid(){

        rows = new TreeMap();
        columns = new TreeMap();
        squares = new TreeMap();
 
        possibleValues = new LinkedList();
        
        unsolvedCells = 81;

        for(int i = 0; i<81; i++){

            int rowN = i;
            int colN = colN_from_rowN(rowN);
            int sqrN = sqrN_from_rowN(rowN);

            Cell c = new Cell(rowN, colN, sqrN, 9);

            rows.put(rowN, c);
            columns.put(colN, c);
            squares.put(sqrN, c);

            possibleValues.add(c);
        }

    }
    
    /** Constructor which calls default constructor and fills given number
     * of random cells with random values (without breaking game rules).
     * User can't change those cells values. They are starting conditions.
     * @param num Number of empty cells to be randomly filled. */
    public DataGrid(int num){
        this();
        addCorrectNumber(num, false);
    }
    
    /** Constructor which creates a copy of another DataGrid by taking data from
     * copied DataGrid.rows map of that DataGrid. Gets called by DataGrid.clone() method.
     * Copy map assumed to be valid.
     * @param Copy Copied DataGrid.rows map from which data for this DataGrid will 
     * be taken. */
    public DataGrid(TreeMap Copy){
        
        rows = Copy;
        columns = new TreeMap();
        squares = new TreeMap();
 
        possibleValues = new LinkedList();
        
        unsolvedCells = 81;

        for(int i = 0; i<81; i++){

            int rowN = i;
            int colN = colN_from_rowN(rowN);
            int sqrN = sqrN_from_rowN(rowN);

            Cell c = rows.get(i);

            columns.put(colN, c);
            squares.put(sqrN, c);

            possibleValues.add(c);
            
            if (c.getValue() != 0) unsolvedCells--;
        }
    }

    /** Private method returns cell column number from given row cell number.*/
    private int colN_from_rowN(int rN){
        return (rN%9)*9 + (rN/9);
    }

    /** Private method returns cell square number from given row cell number.*/
    private int sqrN_from_rowN(int rN){
        return (rN/27)*27 + ((rN%9)/3)*9 + ((rN/9)%3)*3 + (rN%3);
    }

    /** One possible approach to solve the game board. Good for solving
    *   half-filled boards. Bad for filling initially empty boards.  
    *   @todo Need to implement different one.*/
    public void addCorrectNumber(int num, boolean access){
    
        for(int i=0; i<num; i++){

            Collections.sort(possibleValues);

            int size = possibleValues.get(0).getPossibleValues().size();

            int j = 1;
            while (j<81 && possibleValues.get(j).getPossibleValues().size() == size)
                j++;

            int choise = (int)(j*Math.random());
            
            Cell c = possibleValues.get(choise);
            
            if (c.getPossibleValues().size() !=0) {
                insertValue(c.getRowPosition(),
                    c.getPossibleValues().get((int)(c.getPossibleValues().size()
                    *Math.random())), access);
            }
            
            unsolvedCells--;
        }
    }

    /** Method inserts value in an empty cell to which there is an access.
     Excludes value from possible values of row, line,
     * square neighbors of this cell. Sets given access mode to cell.
     @param rowN Number of cell in row board representation.
     @param value Value to be inserted to the cell.
     @param access Mode of access to be set to the cell.*/
    public boolean insertValue(int rowN, int value, boolean access){
        if (rows.get(rowN).getAccess() && rows.get(rowN).getValue()==0 
                && rows.get(rowN).getPossibleValues().contains(value)){

            rows.get(rowN).setValue(value);
            rows.get(rowN).setAccess(access);

            int rN = (rowN/9)*9;
            for (int i=0; i<9; i++){
                rows.get(rN+i).excludeFromPossibles(value);
            }

            int rC = (colN_from_rowN(rowN)/9)*9;
            for (int i=0; i<9; i++){
                columns.get(rC+i).excludeFromPossibles(value);
            }

            int rS = (sqrN_from_rowN(rowN)/9)*9;
            for (int i=0; i<9; i++){
                squares.get(rS+i).excludeFromPossibles(value);
            }
            unsolvedCells--;
            return true;
        }
        return false;
    }

    /** Erases value from given cell. Ensures that neighboring empty cells of given cell
     * add value of given cell to their 'possibleValues' if it's not blocked by
     * neighbors of those cells. Also ensures that non-empty neighbors of current
     * cell limit 'possibleValue' of given cell after its erasure.
     @param rowN Row number of cell to erase. */
    public void eraseValue(int rowN){
        // Save value for later use.
        int value = rows.get(rowN).getValue();

        rows.get(rowN).eraseValue();
        rows.get(rowN).setAccess(true);

        // Traverse through line of original cell
        int rowStartNumber = (rowN/9)*9;
        for (int i=0; i<9; i++){

            if (rowStartNumber+i != rowN)
            // If we find non-empty cell in the line exclude its value from original cell possible vales.
            if (rows.get(rowStartNumber+i).getValue()!=0)
                rows.get(rowN).excludeFromPossibles(rows.get(rowStartNumber+i).getValue());
            else { /** For each empty cell found while traversing row, we need
             * to check if 'value' is present in column and square neighbors of
             found cell. If not, add 'value' to 'possibleValues' of found cell.*/
                boolean found = false;
                int j=0;
                int _columnStNum = (colN_from_rowN(rowStartNumber+i)/9)*9;
                int _squareStNum = (sqrN_from_rowN(rowStartNumber+i)/9)*9;
                while (!found && j<9){
                    if (columns.get(_columnStNum+j).getValue()==value) found = true;
                    if (squares.get(_squareStNum+j).getValue()==value) found = true;
                    j++;
                }
                if (!found) rows.get(rowStartNumber+i).addToPossibleValues(value);
            }
        }

        // Traverse through column of original cell
        int columnStartNumber = (colN_from_rowN(rowN)/9)*9;
        for (int i=0; i<9; i++){

            if (columnStartNumber+i != colN_from_rowN(rowN))
            // If we find non-empty cell in the line exclude its value from original cell possible vales.
            if (columns.get(columnStartNumber+i).getValue()!=0)
                columns.get(colN_from_rowN(rowN)).excludeFromPossibles(columns.get(columnStartNumber+i).getValue());
            else { /** For each empty cell found while traversing column, we need
             * to check if 'value' is present in row and square neighbors of
             found cell. If not, add 'value' to 'possibleValues' of found cell.*/
                boolean found = false;
                int j=0;
                int _rowStNum = (columns.get(columnStartNumber+i).getRowPosition()/9)*9;
                int _squareStNum = (columns.get(columnStartNumber+i).getSqrPosition()/9)*9;
                while (!found && j<9){
                    if (rows.get(_rowStNum+j).getValue()==value) found = true;
                    if (squares.get(_squareStNum+j).getValue()==value) found = true;
                    j++;
                }
                if (!found) columns.get(columnStartNumber+i).addToPossibleValues(value);
            }
        }

        // Traverse through square of original cell
        int squareStartNumber = (sqrN_from_rowN(rowN)/9)*9;
        for (int i=0; i<9; i++){

            if (squareStartNumber+i != sqrN_from_rowN(rowN))
            // If we find non-empty cell in the line exclude its value from original cell possible vales.
            if (squares.get(squareStartNumber+i).getValue()!=0)
                squares.get(sqrN_from_rowN(rowN)).excludeFromPossibles(squares.get(squareStartNumber+i).getValue());
            else { /** For each empty cell found while traversing column, we need
             * to check if 'value' is present in row and square neighbors of
             found cell. If not, add 'value' to 'possibleValues' of found cell.*/
                boolean found = false;
                int j=0;
                int _rowStNum = (squares.get(squareStartNumber+i).getRowPosition()/9)*9;
                int _columnStNum = (squares.get(squareStartNumber+i).getColumnPosition()/9)*9;
                while (!found && j<9){
                    if (rows.get(_rowStNum+j).getValue()==value) found = true;
                    if (columns.get(_columnStNum+j).getValue()==value) found = true;
                    j++;
                }
                if (!found) squares.get(squareStartNumber+i).addToPossibleValues(value);
            }
        }
    }

    /** Method used to help in development. Print values of cells on the board.*/
    public void printGrid(){
        int ch=0;
        int ln =0;
        for (int i=0; i<81; i++){
            if (rows.get(i).getValue() != 0) {
            System.out.print(rows.get(i).getValue());
            } else System.out.print(" ");
            ch++;
            if (ch==3 || ch==6) System.out.print(" ");
            if (ch==9) {
                System.out.println();
                ch=0;
                ln++;
            }
            if (ln == 3){
                System.out.println();
                ln=0;
            }
        }
    }

    /** Returns list with all cell values given in row oriented board order.*/
    public LinkedList<Integer> getValues(){
        LinkedList<Integer> list = new LinkedList();

        for (int i=0; i<81; i++){
            list.add(rows.get(i).getValue());
        }

        return list;
    }

    /** Returns list with all cell access modes
     * given in row oriented board order.*/
    public LinkedList<Boolean> getAccess(){
        LinkedList<Boolean> list = new LinkedList();

        for (int i=0; i<81; i++){
            list.add(rows.get(i).getAccess());
        }

        return list;
    }
    
    /** Method needed by Cloneable interface, returns a valid clone of this 
     * DataGrid.*/
    @Override
    public DataGrid clone(){
        
        TreeMap<Integer, Cell> copyMap = new TreeMap();
        
        for (int i = 0; i<81; i++){
            copyMap.put(i, rows.get(i).clone());
        }
        
        DataGrid copy = new DataGrid(copyMap);
        
        return copy;
    }
}
